package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 200. 岛屿数量
 * @date 2025/1/25 13:15
 */
public class E200 {

    /**
     * <h3>方法一：深度优先遍历</h3>
     *
     * @param grid 二维数组
     * @return 岛屿数量
     */
    public int numIslands(char[][] grid) {
        // 1. 初始化变量
        int rows = grid.length, cols = grid[0].length, count = 0;
        // 2. 二维数组visited，用于存储是否访问过，只针对于1（陆地），不针对0
        boolean[][] visited = new boolean[rows][cols];
        // 3. 遍历二维数组，统计岛屿数量
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // 4. 如果当前位置是陆地，并且没有被访问过，则进行深度优先遍历，将该陆地所在岛屿标记为访问状态，岛屿数量加1
                if (grid[i][j] == '1' && !visited[i][j]) {
                    dfs(grid, i, j, visited);
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * 深度优先遍历
     *
     * @param grid    二维数组
     * @param i       当前行
     * @param j       当前列
     * @param visited 二维数组visited，用于存储是否访问过，只针对于1（陆地），不针对0
     */
    private void dfs(char[][] grid, int i, int j, boolean[][] visited) {
        // 1. 递归结束条件：边界条件，越界、当前位置不是陆地、当前位置已经被访问过
        if (i < 0 || j < 0
                || i >= grid.length || j >= grid[0].length
                || grid[i][j] == '0' || visited[i][j]) return;
        // 2. 标记当前陆地为已访问
        visited[i][j] = true;
        // 3. 递归遍历上左下右，深度搜索
        dfs(grid, i - 1, j, visited);
        dfs(grid, i, j - 1, visited);
        dfs(grid, i + 1, j, visited);
        dfs(grid, i, j + 1, visited);
    }
}
